/*
 * @lc app=leetcode.cn id=20 lang=cpp
 *
 * [20] 有效的括号
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <cmath>

using namespace std;
// @lc code=start
class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        int n = s.length();
        st.push(s[0]);
        for(int i = 1;i < n;i++) {
            if(!st.empty()) {
                char c = st.top();
                if((s[i] == ')' && c == '(') ||(s[i] == ']' && c == '[')|| (s[i] == '}' && c == '{') ) {
                    st.pop();
                }else {
                    st.push(s[i]);
                }
            }else {
                st.push(s[i]);
            }
        }
        return st.empty();
    }
};
// @lc code=end

